package leetcode.list;

import utils.node.ListNode;

/**
 * @Description: https://leetcode.cn/problems/partition-list/
 * @Author Ammar
 * @Create 2023/7/10 18:44
 */
public class _86_分隔链表 {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode headl = new ListNode(0);
        ListNode taill = headl;

        ListNode headr = new ListNode(0);
        ListNode tailr = headr;

        while (head != null) {
            if (head.val < x) {
                taill.next = head;
                taill = taill.next;
            } else {
                tailr.next = head;
                tailr = tailr.next;
            }
            head = head.next;
        }
        taill.next = headr.next;
        tailr.next = null;
        return headl.next;
    }
}
